#include <bits/stdc++.h>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL){}
                                              
};
class Solution
{
public:
    TreeNode *reCreateBTree(vector<int> pre, int pre_begin, int pre_end, vector<int> vin, int vin_begin, int vin_end)
    {
        if (pre_begin > pre_end || vin_begin > vin_end)
        {
            return nullptr;
        }
        TreeNode *root = new TreeNode(pre[pre_begin]);
        for (int i = vin_begin; i <= vin_end; i++)
        {
            if (vin[i] == pre[pre_begin])
            {
                root->left = reCreateBTree(pre, pre_begin + 1, pre_begin + 1 + i - vin_begin - 1, vin, vin_begin, i - 1);
                root->right = reCreateBTree(pre, pre_begin + i - vin_begin + 1, pre_end, vin, i + 1, vin_end);
                break;
            }
        }
        return root;
    }
    TreeNode *reConstructBinaryTree(vector<int> pre, vector<int> vin)
    {
        if (pre.size() == 0)
        {
            return nullptr;
        }
        return reCreateBTree(pre, 0, pre.size() - 1, vin, 0, vin.size() - 1);
    }
};